package com.zyj.test.month1.day3;

import com.zyj.test.TreeNode;

import java.util.*;

/**
 * @author Yijia Zhang
 * @create 2024-04-24 23:00
 */
public class code2358 {
    //将树转换成图进行宽度优先搜索
    public int amountOfTime(TreeNode root, int start) {
        if (root == null) {
            return 0;
        }
        Map<Integer, Integer> nodes = new HashMap<>();
        int idx = 0;
        List<List<Integer>> edges = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int startIdx = -1;
        while (!queue.isEmpty()) {
            TreeNode peek = queue.poll();
            if (peek.val == start) {
                startIdx = idx;
            }
            if (peek.left != null) {
                queue.offer(peek.left);
            }
            if (peek.right != null) {
                queue.offer(peek.right);
            }
            nodes.put(peek.val, idx++);
        }

        //共有idx个节点
        for (int i = 0; i < idx; i++) {
            edges.add(new ArrayList<>());
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode peek = queue.poll();

            if (peek.left != null) {
                edges.get(nodes.get(peek.val)).add(nodes.get(peek.left.val));
                edges.get(nodes.get(peek.left.val)).add(nodes.get(peek.val));
                queue.offer(peek.left);
            }
            if (peek.right != null) {
                edges.get(nodes.get(peek.val)).add(nodes.get(peek.right.val));
                edges.get(nodes.get(peek.right.val)).add(nodes.get(peek.val));
                queue.offer(peek.right);
            }

        }
        //转成图了，开始宽度优先搜索
        int res = -1;
        Set<Integer> set = new HashSet<>();
        set.add(startIdx);
        Queue<Integer> queue2 = new LinkedList<>();
        queue2.offer(startIdx);
        while (!queue2.isEmpty()) {
            int size = queue2.size();
            for (int i = 0; i < size; i++) {
                int peek = queue2.poll();
                for (Integer integer : edges.get(peek)) {
                    if (!set.contains(integer)) {
                        queue2.offer(integer);
                        set.add(integer);
                    }
                }
            }
            res++;
        }
        return res;
    }

}
